package com.leetcode;

import java.util.*;

public class Leetcode051 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        //横线不用判断，因为行只会添加一个
        //竖线
        Set<Integer> columns = new HashSet<Integer>();
        //对角线“捺”
        Set<Integer> diagonals1 = new HashSet<Integer>();
        //对角线“撇”
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    private void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            //i表示第几个Q,轮询的次数是 N!,例如N=4,表示要进行4*3*2*1次循环
            //i也表示第几列
            for (int i = 0; i < n; i++) {
                //同一列中，不能存在两个Q
                if (columns.contains(i)) {
                    continue;
                }
                //“捺”线规律：row - column等于常量，表示在同一条斜线,同一斜线不能存在两个Q
                //并且如果有 4个Q，相当于有四条“捺”线
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                //“撇”线规律：row + column等于常量，表示在同一条斜线，同一个斜线不能存在两个Q
                //并且如果有 4个Q，相当于有四条“撇”线
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }

                //先假设当前位置可以放置Q，
                //queens[row]记录的是每一行i的位置，用来生成最后的结果。
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                //将columns, diagonals1, diagonals2标记传给下一行
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);

                queens[row] = -1;
                //每次回退上次循环记录的值，开始放置Q的下一个可能位置
                //例如：当前准备放置第三个Q的位置，那么就删除第三个Q的位置信息,前面已经存放的Q信息不动
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    private List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }


    public static void main(String[] args) {
        Leetcode051 leetcode051 = new Leetcode051();
        System.out.println(leetcode051.solveNQueens(4));
    }
}
